Mark-sweep or copying?: a ”best of both worlds” algorithm and a hardware-supported real-time implementation

Copying collectors offer a number of advantages over their mark-sweep counterparts. First, they do not have to deal with mark stacks and potential mark stack overflows. Second, they do not suffer from unpredictable fragmentation overheads since they inherently compact the heap. Third, the tospace invariant maintained by many copying collectors allows for incremental compaction and provides the basis for efficient real-time implementations. Unfortunately, however, standard copying collectors depend on two semispaces and therefore need at least twice as much memory as required for the maximum amount of live data. In this paper, we introduce a novel mark-compact algorithm that combines the elegance and simplicity of Baker’s copying algorithm with the memory efficiency of mark-sweep algorithms. Further-more, we present a hardware-supported implementation for real-time applications in the framework of an object-based RISC archi-tecture. Measurements of Java programs on an FPGA-based prototype show that our novel mark-compact algorithm outperforms a cor-responding copying collector in every respect. It requires far less memory space for real-time behavior and, at the same time, reduces the overall runtime overhead under typical operating conditions